package com.sicheng.algorithm.并查集;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/30 23:01
 */
@SuppressWarnings("unused")
public class 并查集 {
    int[] p = new int[10000];

    //初始化，现在各自为王，自己就是一个集合
    void init() {
        for (int i = 0; i < 10; i++) {
            p[i] = i;
        }
    }

    //查询根结点
    int find(int x) {
        if (p[x] == x)
            return x;

        p[x] = find(p[x]);   //顺便把双亲结点也设置为根结点，路径压缩
        return p[x];

    }

    //合并,把 j 合并到 i 中去，就是把j的双亲结点设为i
    void merge(int i, int j) {
        p[find(j)] = find(i);
    }

    public static void main(String[] args) {
        并查集 bin = new 并查集();
        bin.init();
        bin.merge(1, 3);
        bin.merge(1, 4);
        bin.merge(4, 5);
    }

}
